package q547_findCircleNum;


public class Solution_1 {

    /*
    此题的矩阵表示的一种相连关系
    因此使用dfs需要一个linked来记录当前城市是否已经与此前遍历的城市相连
     */
    public int findCircleNum(int[][] isConnected) {
        int province = 0;
        boolean[] linked = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!linked[i]) {
                dfs(isConnected, linked, i);
                province++;
            }
        }
        return province;
    }

    /*
    关键在于 当传入一个城市的i时 需要将所有与该城市直接和 间接 相连的城市都标记为linked 所以需要dfs
     */
    private void dfs(int[][] isConnected, boolean[] linked, int curr) {
        for (int i = 0; i < isConnected.length; i++) {
            if (isConnected[curr][i] == 1 && !linked[i]) {
                linked[i] = true;
                dfs(isConnected, linked, i);
            }
        }
    }
}
